import math
import random

def euclidean_distance(point1, point2):
    # 计算欧氏距离
    return math.sqrt(sum((a - b) ** 2 for a, b in zip(point1, point2)))

def assign_cluster(x, c):
    # 将样本x分配到最近的中心点c
    min_distance = float('inf')
    cluster_index = 0

    for i, centroid in enumerate(c):
        distance = euclidean_distance(x, centroid)
        if distance < min_distance:
            min_distance = distance
            cluster_index = i

    return cluster_index

def Kmeans(data, k, epsilon=1e-4, iteration=100):
    # 随机初始化中心点
    centroids = random.sample(data, k)

    for iter_count in range(iteration):
        # 分配样本到簇
        clusters = [assign_cluster(point, centroids) for point in data]

        # 更新中心点
        new_centroids = []
        for i in range(k):
            cluster_points = [data[j] for j in range(len(data)) if clusters[j] == i]
            if cluster_points:
                dimension = len(data[0])
                new_centroid = [sum(point[d] for point in cluster_points) / len(cluster_points)
                                for d in range(dimension)]
                new_centroids.append(new_centroid)
            else:
                new_centroids.append(random.choice(data))

        # 检查收敛
        max_change = max(euclidean_distance(centroids[i], new_centroids[i])
                         for i in range(k))
        if max_change < epsilon:
            break

        centroids = new_centroids

    return centroids, clusters